In recent years, various kinds of information such as characters, images, and voices are digitized to be used in accordance with rapid development and spread of computers and networks. Digitized information (digital data) has characteristics that it is not affected by deterioration due to aging or the like and can be preserved in a perfect state forever, and on the other hand, it is possible to subject the data to editing or processing easily.
The characteristic that editing and processing of the digital data is easy is useful for users. However, for example, reliability of digital data is low compared with conventional analog data for insurance companies handling photographs of evidence for settlement of accidents, construction companies handling records of progress in building sites, and the like. This leads to a problem in that the digital data is poor in admissibility as evidence.
Thus, there has been proposed an apparatus or a system which, in the case in which the digital data is falsified or forged, detects the falsification or the forgery. For example, a system utilizing digital signature is well known as a system for detecting falsification and forgery of the digital data.
Here, the digital signature means a function with which a transmission side sends object data together with signature data (digital signature data) corresponding to the object data and a reception side verifies this signature data, thereby confirming legality of the object data.
For example, processing from generating digital signature data using a Hash function and a public key cipher on the transmission side to confirming legality of this digital signature data on the reception side is carried out as described below.
First, assuming that a secret key is Ks and a public key (decryption key) is Kp, the transmission side (origination side) compresses plain text data M with the Hash function, and executes arithmetic operation processing for calculating an output h of a constant length (e.g., 128 bits).
Next, the transmission side converts the output h with the secret key Ks and executes arithmetic operation processing for generating a result of the conversion as digital signature data s, that is, arithmetic operation processing in accordance with expression D (Ks, H)=s. Then, the transmission side sends the digital signature data s and the plain text data M to the reception side.
The reception side executes arithmetic operation processing for converting the digital signature data s sent from the transmission side with the public key Kp, that is, arithmetic operation processing in accordance with expression E (Kp, s)=E (Kp, D (Ks, h″))=h″, andarithmetic operation processing for compressing plan text data M′ sent from the transmission side (received plain text data is assumed to be M′ because the plain text data M sent on the transmission side may be falsified) with the same function as the Hash function used on the transmission side to calculate h′. In the case in which h′ and h″, which are results of the arithmetic operation processing, coincide with each other, the reception side determines that the received plain data text M′ is legal data. That is, in the case in which the plan text data M is falsified between the transmission side and the reception side, this falsification can be detected because h′ and h″ do not coincide with each other.
In this case, it is possible that, if the digital signature data s is also falsified in addition to the falsification of the plain text data M, the falsification cannot be detected. However, the possibility is denied because it is necessary to find the plain text data M from the output h and due to unidirectionality of the Hash function to be described later in detail.
It becomes possible to perform authentication of data correctly according to the digital signature using the public key cipher and the Hash function as described above.
The public key cipher and the Hash function will be described. First, the Hash function is a function which is used for, for example, speeding up generation of digital signature, and has a function for transforming the plain text data M of an arbitrary length into the data h of a fixed length. This output data h is called a Hash value (or message digest, or digital fingerprint) of the plain text data M.
Examples of characteristics required of the Hash function include characteristics that unidirectionality and collision tolerance are required.
The unidirectionality is a characteristic that, when the data h is given, it is difficult to calculate the plain text data M satisfying h=H (M) in terms of computational complexity. The collision tolerance is a characteristic that, when the plain text data M is given, it is difficult to calculate the plain text data M′ (M≠M′) satisfying H (M)=H (M′) in terms of computational complexity and it is difficult to calculate the plain text data M and M′ satisfying H (M)=H (M′) and M≠M′ in terms of computational complexity.
As the Hash function, there are known, for example, MD-2, MD-4, MD-5, SHA-1, RIPEMD-128, or RIPEMD-160. These algorisms have been laid open to the public.
On the other hand, a public key cryptosystem is a cryptosystem in which an encryption key and a decryption key are different and the encryption key is laid open and the decryption key is kept secret. Examples of characteristics of such a public key cryptosystem include characteristics (a) to (c) described below.
(a) Since the encryption key and the decryption key are different and the encryption key can be laid open to the public, it is unnecessary to deliver the encryption key secretly and key delivery is easy.
(b) Since an encryption key of each user is laid open, the user only has to store the user's own decryption key in secret.
(c) An authentication function can be realized with which the reception side can confirm that the transmission side of a communication text (plain text data M) is not a pretender and that the communication text is not falsified.
More specifically, for example, if an encryption operation using the public encryption key (public key) Kp with respect to the plain text data M is represented by E (Kp, M) and a decryption operation using the secret decryption key (secret key) Ks with respect to the plain text data M′ encrypted by this encryption operation is represented by D (Ks, M′), first, a public key encryption algorism satisfies two conditions (1) and (2) described below.
(1) Calculation of E (Kp, M) is easy when the public key Kp is given, and calculation of D (Ks, M′) is easy when the secret key Ks is given.
(2) If the secret key Ks is unknown, it is difficult to determine the plain text data M in terms of computational complexity even if the public key Kp, calculation procedures for E (Kp, M), and M′ (=E (Kp, M)) are known. If the public key encryption algorism satisfies a condition (3) described below in addition to the conditions (1) and (2), secret communication becomes possible.
(3) E (Kp, M) can be defined for all the plain text data M, and D (Ks, E (HP, M))=M is established. That is, since the public key Kp is laid open, anybody can calculate E (Kp, M). However, only a user himself/herself having the secret key Ks can calculate D (Ks, E (Hp, M)) to obtain the plain text data M.
In addition, if the public key encryption algorism satisfies a condition (4) described below in addition to the conditions (1) and (2), authentication communication can be realized.
(4) D (Ks, M′) can be defined for all the plain text data M′, and E (Kp, D (Ks, M′))=M′ is established. That is, only a user himself/herself having the secret key Ks can calculate D (Ks, M′) and, even if another user uses a false secret key Ks′ to calculate D (Ks′, M) and pretends to be the user himself/herself having the secret key Ks, since E (Kp, D (Ks′, M′))≠M′, the reception side can confirm that the received data is illegal. In addition, even if D (Ks, M′) is falsified, since E (Kp, D (Ks, M′)′)≠M′, the reception side can confirm that the received data is illegal.
Representative examples of a cryptosystem capable of carrying out the secret communication and authentication communication as described above include RSA encryption, R encryption, W encryption, or the like. For example, encryption and decryption in the RSA cryptosystem, which is used most frequently presently, are represented by expressions as described below.
Encryption conversion using an encryption key (e, n) is represented by expression C=M (e mod n), and conversion for decrypting this with a decryption key (d, n) is represented by expression M=C (d mod n).
In addition, n=p·q, where p and q are prime numbers of different sizes, respectively.
However, since the RSA cryptosystem requires an exponential operation and a remainder operation as indicated in the above expressions, an amount of operation becomes enormous compared with a common key cipher such as DES, and it is difficult to speed up processing for the encryption and the decryption.
A system for verifying, for example, falsification and forgery of image data utilizing the digital signature described above is disclosed in U.S. Pat. No. 5,499,294 and the like. This system is constituted such that processing as described below is carried out.
First, a Hash value of image data to be an object (object image data) is calculated and the Hash value is encrypted with a secret key, whereby a digital signature for the object image data is generated. Next, in order to verify whether or not the object image data is falsified, the digital signature for the object image data is decrypted with a public key, whereby a Hash value is calculated. Moreover, a Hash value is also calculated from the object image data. Then, the Hash value obtained by decrypting the digital signature for the object image data and the Hash value obtained from the object image data are compared. As a result of this comparison, if both the Hash values coincide with each other, it is verified that the object image data is neither falsified nor forged.
The technique described in U.S. Pat. No. 5,499,294 is also applicable to the case in which data to be an object of signature is not image data and the image data is compression-coded data. Since signature processing has a characteristic that a processing time increases in proportion to a capacity of data to be inputted (signed data), it is preferable to apply the signature processing to the compression-coded data from the viewpoint of reducing a signature processing time.
Incidentally, the compression coding can be classified into lossy coding involving image deterioration and lossless coding not involving image deterioration in the case in which image data before coding and image data after decoding are compared. The lossless coding does not involve image deterioration but has a degree of freedom in coding parameters. In the case in which lossless coding processing is executed with respect to certain image data using coding parameters different from each other, two different compression-coded image data is generated (images obtained by decoding the two image data are completely the same). This poses a problem because, in the case in which lossless compression-coded data is used as signed data, the data may be considered falsified even if contents of the images are not falsified.
The present invention has been devised in view of the above problems, and it is an object of the present invention to provide a technique for verifying presence or absence of falsification with respect to compression-coded data subjected to lossless compression coding using compression coding parameters different from each other.